#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void get_next(const char *needle, int *next)
{
    int j, k, nsize;
    
    next[0] = -1;
    nsize = strlen(needle);

    j = 0, k = -1;
    while(j < nsize - 1)
    {
        if (k == -1 || needle[k] == needle[j])
        {
            k ++;
            j ++;
            if (needle[k] != needle[j])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
            k = next[k];
    }
}

static int kmp(const char *haystack, const char *needle)
{
    int i, j, nsize;
    int *next;

    if (haystack == NULL || needle == NULL)
        return -1;
    
    nsize = strlen(needle);
    next = malloc(nsize * sizeof(int));
    get_next(needle, next);
    
    i = j = 0;
    while (haystack[i] != '\0' && j < nsize)
    {
        if (j == -1 || haystack[i] == needle[j])    
        {
            i ++;
            j ++;
        }
        else
            j = next[j];
    }

    free(next);

    if (haystack[i] != '\0')
        return i - nsize;    
    else
        return -1;
}

int main(int argc, char const* argv[])
{
    char *s = "012345678901234567890123456789";
    char *p = "901";
    printf("s is %s\n", s);
    printf("find %s in s is %d\n", p, kmp(s, p));

    p = "01235";
    printf("find %s in s is %d\n", p, kmp(s, p));

    p = "012";
    printf("find %s in s is %d\n", p, kmp(s, p));

    return 0;
}
